class Solution {
public:
    string reverseWords(string s) {
        s = trim(s);
        char* chars = &s[0];
        reverse(chars, 0, s.length() - 1);
        reverseEachWord(chars, s.size());
        return s;
    }

    void reverse(char* chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    string reverseEachWord(char* chars, int n) {
        int slow = 0, fast = 0;
        while (fast < n) {
            while (fast < n && chars[fast] != ' ') fast++;
            reverse(chars, slow, fast - 1);
            fast++;
            slow = fast;
        }

       return string(chars);
    }

    // 删除字符串中所有的空字符，但是单词之间需要一个空字符隔开
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)，原地删除空字符
    string trim(string s) {
        char* chars = &s[0];
        int n = s.size();
        int slow = 0, fast = 0;

        while (fast < n) {
            if (chars[fast] != ' ' || (fast >= 1 && chars[fast - 1] != ' ')) {
                chars[slow] = chars[fast];
                slow++;
            }
            fast++;
        }

        if (slow >= 1 && chars[slow - 1] == ' ') slow--;

        return string(chars, slow);
    }
};